package com.base.hot;

import java.util.*;

public class GroupAnagrams {
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(strs));
    }

    /**
     * 1 <= strs.length <= 104
     * 0 <= strs[i].length <= 100
     * strs[i] 仅包含小写字母
     *
     * @param strs
     * @return
     */
    private static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        if (strs.length == 0) {
            return list;
        }
        int[] visited = new int[strs.length];
        //怎么判断是两个字符串是同字母异序词
        for (int i = 0; i < strs.length; i++) {
            if (visited[i] == 1) {
                continue;
            }
            List<String> item = new ArrayList<>();
            for (int j = i + 1; j < strs.length; j++) {
                if (visited[j] == 1) {
                    continue;
                }
                if (isAnagram(strs[i], strs[j])) {
                    item.add(strs[j]);
                    visited[j] = 1;
                }
            }
            item.add(strs[i]);
            list.add(item);
        }
        return list;

    }

    private static List<List<String>> groupAnagramsV2(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs){
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            map.computeIfAbsent(new String(chars), k -> new ArrayList<>()).add(s);
        }
        map.forEach((k, v) -> list.add(v));
        return list;
    }

    /**
     * 是否同字母异序词
     *
     * @param str
     * @param str1
     * @return
     */
    private static boolean isAnagram(String str, String str1) {
        if (str.length() != str1.length()) {
            return false;
        }
        int[] count = new int[26]; // 只使用 26 个字母的计数
        for (char c : str.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : str1.toCharArray()) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}
